#include <iostream>
#include <string>
#include <map>

class Solution1
{
public:
    int lengthOfLongestSubstring(std::string s)
    {
        int MAX = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            int max = 1;
            std::string subs = std::string(1, s[i]);
            for (int j = i + 1; j < s.size(); ++j)
            {
                if (subs.find(s[j]) == -1)
                {
                    subs += s[j];
                    max++;
                }
                else
                {
                    break;
                }
            }
            if (max > MAX)
            {
                MAX = max;
            }
        }

        return MAX;
    }
};

class Solution
{
public:
    int lengthOfLongestSubstring(std::string s)
    {
        std::map<char, int> m;
        int begin = 0, max = 0, sublen = 0;
        int Length = s.size();
        for (int i = 0; i < Length; ++i)
        {
            if (m.find(s[i]) == m.end() || m[s[i]] < begin)
            {
                sublen++;
            }
            else
            {
                int pos = m[s[i]];
                max = std::max(max, sublen);
                sublen = sublen - (pos - begin);
                begin = pos + 1;
            }
            // 如果前面有相同的key值，会进行覆盖。
            m[s[i]] = i;
        }
        max = std::max(max, sublen);

        return max;
    }
};

int main(int argc, char **argv)
{
    std::string s = "dvdf";
    std::cout << Solution().lengthOfLongestSubstring(s) << std::endl;

    return 0;
}
